package com.linyaonan.leetcode.sword_to_offer._21;

import java.util.ArrayList;

/**
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
 *
 *  
 *
 * 示例：
 *
 * 输入：nums = [1,2,3,4]
 * 输出：[1,3,2,4]
 * 注：[3,1,2,4] 也是正确的答案之一。
 *  
 *
 * 提示：
 *
 * 0 <= nums.length <= 50000
 * 0 <= nums[i] <= 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    /**
     * 暴力解法：使用两个队列存储奇数与偶数，最后组合
     * @param nums
     * @return
     */
    public int[] exchange(int[] nums) {
        if (nums == null) {
            return nums;
        }
        if (nums.length < 2) {
            return nums;
        }

        ArrayList<Integer> j = new ArrayList<>();
        ArrayList<Integer> o = new ArrayList<>();

        for (int num : nums) {
            int t = num & 1;
            if (t == 1) {
                j.add(num);
            } else {
                o.add(num);
            }
        }

        int[] r = new int[nums.length];
        int index = 0;
        for (Integer jj : j) {
            r[index++] = jj;
        }
        for (Integer oo : o) {
            r[index++] = oo;
        }

        return r;
    }

    /**
     * 双指针法：
     * 1. 左指针找到首个偶数，右指针找到首个奇数，原地交换
     * 2. 指针相遇后结束
     * @param nums
     * @return
     */
    public int[] exchange2(int[] nums) {
        if (nums == null) {
            return nums;
        }
        if (nums.length < 2) {
            return nums;
        }

        int l = 0;
        int r = nums.length - 1;

        while (l < r) {
            int p1 = nums[l] & 1;
            int p2 = nums[r] & 1;
            // 找到
            if (p1 == 0 && p2 != 0) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                l++;
                r--;
            } else {
                if (p1 != 0) {
                    l++;
                }
                if (p2 == 0) {
                    r--;
                }
            }
        }

        return nums;
    }
}